#include "game.h"
#include<bits/stdc++.h>
using namespace std;

mt19937 mt_rand;
int cnt,cur[5005];
bool vis[5005][5005],qwq[5005];
int lt[5005];

vector<int> qry;

std :: vector<int> guess(int n, int limit) {
    srand(time(0));
    mt_rand.seed(rand());

	qry.resize(n);
    for(int i=1;i<=n;i++)
        qry[i-1]=i;

    for(int i=1;i<=n;i++)
        cur[i]=n;

    while(1)
    {
        shuffle(qry.begin(),qry.end(),mt_rand);

        for(int i=1;i<=n;i++)
        {
            if(lt[qry[i-1]])
                swap(qry[i-1],qry[lt[qry[i-1]]-1]);
        }

        int res=count(qry);

        if(res==n)
            return qry;

        if(res==cnt)
        {
            for(int i=1;i<=n;i++)
            {
                if(cur[i]==1&&qwq[i])
                    continue;

                if(vis[i][qry[i-1]])
                    continue;

                vis[i][qry[i-1]]=1,cur[i]--;
                if(cur[i]==1)
                {
                    qwq[i]=1;
                    cnt++;
                    for(int j=1;j<=n;j++)
                    {
                        if(!vis[i][j])
                        {
                            lt[j]=i;
                            for(int k=1;k<=n;k++)
                            {
                                if(!vis[k][j])
                                    vis[k][j]=1,cur[k]--;
                            }
                            break;
                        }
                    }
                }
            }
        }

        while(1)
        {
            int lx=cnt;

            for(int i=1;i<=n;i++)
            {
                if(cur[i]==1&&qwq[i])
                    continue;

                if(cur[i]!=1)
                    continue;

                qwq[i]=1;
                cnt++;
                for(int j=1;j<=n;j++)
                {
                    if(!vis[i][j])
                    {
                        lt[j]=i;
                        for(int k=1;k<=n;k++)
                        {
                            if(!vis[k][j])
                                vis[k][j]=1,cur[k]--;
                        }
                        break;
                    }
                }
            }

            if(lx==cnt)
                break;
        }
    }
}

